• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    The present invention relates to caches, methods and systems for using an invalidation data area. The cache may include a log configured to track data blocks, and an invalidation data area configured to track invalid data blocks associated with the data blocks tracked in the log. The invalidation data area may be in a separate cache region of the log. The method for disabling a cache block may include determining a log block according to a memory address associated with a received write operation. The method may also include determining a log block mapped based on the log block and an invalidation record. The method may also include determining whether write operations are pending. If so, the method may include aggregating the outstanding write operations and performing a single write operation based on the aggregated write operations.
    公开号:FR3023030A1
    申请号:FR1555325
    申请日:2015-06-11
    公开日:2016-01-01
    发明作者:Pulkit Misra
    申请人:HGST Netherlands BV；
    IPC主号:
    专利说明:

    [0001] BACKGROUND OF THE INVENTION The present invention relates to caching systems and methods, and more particularly is directed to providing a region for processing invalidated data for a cache. Background A cache can usually be used to speed up access when reading or writing data to an underlying storage, such as a flash memory or hard disk. Upon receipt of a write operation from a host, the cache may update a stored data block to determine if the data block has changed (for example, if the data block is valid or invalid). Sometimes the cache can write new data from the write operation to another cache entry, and defer evicting or removing the old cache entry. This is because evicting or removing the old cache entry may result in performance declines while the cache is waiting for the underlying storage to be updated. Using this report allows the cache to complete processing of the write operation and return control to the host earlier. SUMMARY Embodiments of the present invention relate to caches, methods, and systems for using an invalidation data area.
    [0002] In one embodiment, the present disclosure relates to a cache. The cache may include a log and an invalid data field. The log can be configured to track blocks of data stored in the cache. The invalidation data area may be configured to track invalid data blocks associated with the data blocks tracked in the log, the invalidation data area being in a region separate from the cache relative to the log. In one embodiment, the present invention relates to a method for invalidating a block in a cache memory. The method may include determining a log block according to a memory address associated with a received write operation, the log block being stored in a cache log. The method may also include determining a log block mapped based on the determined log block and further based on an invalidation record, the mapped log block and the invalidation record being stored in a data area. invalidating the cache. The method may also include determining whether write operations are pending. If write operations are pending, the method may include aggregating the outstanding write operations and performing a single write operation based on the aggregated write operations. If no write operation is pending, the method may include executing the received write operation. In one embodiment, the present invention relates to a method of recovering a cache. The method may include determining an initial reconstruction of the cache memory based on a cache log. For each log block mapped in an invalidation record in a cache invalidation data area, the method may include determining whether a corresponding data block tracked in the log is valid, based on the block of data. log mapped. If the corresponding data block is determined to be invalid, the method may include evicting the corresponding data block from the initial reconstruction of the cache memory. Embodiments described herein may include additional aspects. For example, the log may be configured to track metadata for the data blocks, the metadata may include a memory address corresponding to the data block, and the invalidation data area may be configured to track metadata associated with the blocks. of invalidated data, the associated metadata may include a memory address corresponding to the invalid data block. The log can be configured to track data blocks using log blocks, log blocks can be configured to store metadata for data blocks, and the invalidation data area can be configured for tracking data blocks. metadata associated with invalid data blocks using invalid invalidation records and mapped log blocks, mapped log blocks that can be configured to store metadata associated with invalid data blocks, and invalid invalidation records be configured to store the mapped log blocks. The metadata tracked in the log may further include an index in a set of metadata stored in each log block, and the metadata tracked in the invalidation data field may further include an index in a set of metadata stored in each log block mapped. The cache may be configured to determine an invalidation record number associated with an invalidation record in the invalidation data area based on a corresponding log block number associated with a log block. The cache may be configured to determine a mapped log block number associated with a log block mapped in the invalidation zone based on a corresponding log block number associated with a log block. The index tracked in the log can be selected to have the same value as the index track in the invalid data field. The memory address followed in the invalidation data area may be truncated with respect to the memory address followed in the log, and truncation may be determined based on a storage size of a device. underlying storage being cached or on a determined offset based on a memory address of a block in the underlying storage device. Determining the mapped log block may include determining a mapped log block number for the mapped log block by determining an invalid log number by dividing a log block number associated with the log block determined by a capacity of the invalidation record in the invalidation data area and calculating a cap function of the division result, the invalidation record number identifying the invalidation record, and determining the number of the invalidation record; log block mapped by calculating a modulo operation of the log block number with the ability of the invalidation record. Determining whether write operations are outstanding may include recovering a field of a data structure in RAM memory corresponding to the invalidation record. Aggregating outstanding write operations may include queuing subsequent write operations, identifying write operations that operate on the same data block, and determining the only write operation based on write operations that operate on the same block of data. The invalidation data area may be a region separate from the cache relative to the log. The cache may be a content near cache, and the log may track at least one of the associated data blocks and independent data blocks in the content close cache.
    [0003] Determining the initial reconstruction may include retrieving data blocks and metadata describing the data blocks, retrieved data blocks, and metadata being retrieved from the log. Determining whether the corresponding data block tracked in the log is valid may include comparing metadata describing the corresponding data block tracked in the log to metadata describing the corresponding data block tracked in the mapped log block. Comparing the metadata may include comparing a first memory address and a first index for the corresponding data block tracked in the log to a second memory and a second index track in the mapped log block.
    [0004] BRIEF DESCRIPTION OF THE FIGURES Various objects, features and advantages of the present disclosure may be better appreciated with reference to the following detailed description, taken in conjunction with the following drawings, in which like reference numerals identify like elements. The following drawings are for illustrative purposes only and are not intended to limit the invention, the scope of which is defined in the following claims. Figure 1 illustrates an exemplary system including a cache memory according to some embodiments of the present invention. Figs. 2A-2B illustrate exemplary block diagrams in accordance with some embodiments of the present invention.
    [0005] Figs. 3A-3B illustrate examples of mappings between a log and an invalidation data area, in accordance with some embodiments of the present invention.
    [0006] Fig. 4 illustrates an exemplary invalidation method using the invalidation data area, in accordance with some embodiments of the present disclosure. Figure 5 illustrates an exemplary cache recovery method according to some embodiments of the present disclosure.
    [0007] DETAILED DESCRIPTION The present disclosure relates to systems and methods for using an invalidation data area for a cache. In some embodiments, the cache may include a log area and an invalid data area. The log area can be a log to track cache updates and cache operations persistently, in case there is a need for cache recovery. The invalidation data area may store invalidation records for cache blocks that are removed or removed from the cache. The invalidation data area can generally track information about cached data blocks that have been disabled, for example, when caching is paused or otherwise paused. The invalidation data area may accompany the log area and occupy a region separated from the cache. In addition, some embodiments of the invalidation data area may store a subset of metadata that corresponds to a complete set of metadata typically stored in the log. Figure 1 illustrates an exemplary system 100, including a cache memory 104, according to some embodiments of the present disclosure. The system 100 includes a host 102, a cache 104, and a storage 106a-106c. Host 102 transmits read and write requests to cache 104. Cache 104 processes requests for reading and writing data to and from underlying storage 106a-106c. For example, to process a read request, cache 104 may determine whether data corresponding to a requested memory address is stored in the cache. If the requested memory address is cached, this situation can sometimes be considered a "read success". If the requested memory address is not cached, this situation may be considered a "read failure". After a read success, the cache 104 may return the requested data more quickly directly from the cache 104. On the other hand, during a "read failure", the cache 104 may read the requested data from the slower storage 106a. -106c.
    [0008] Similarly, to process a write request, cache 104 may determine if a requested memory address is already stored in the cache. If the requested memory address is cached, this situation can sometimes be considered a "write success". If the requested memory address is not cached, this situation may be considered a "write failure".
    [0009] Fig. 2A illustrates an exemplary block diagram 104 in accordance with some embodiments of the present invention. In some embodiments, the cache 104 may include a superblock 202, a reference data area 204, a log 206, an invalidation data area 208, and a hot start area 210. The journal 206 may include Log blocks 212 may include metadata 214 and data 216. Cache 104 may use a log-based approach to provide persistence, so that cache 104 may be retrieved when needed. . Some embodiments of the log 206 may be subdivided into log blocks 212. For example, log blocks 212 may be approximately 256 KB in size. Other sizes may also be used in relation to the total size of the cache. 104. If a log block 212 has a size of about 256 KB, the metadata 214 can occupy up to about 4 KB of space and the data 216 can use about 252 KB of space. As before, other sizes may also be used depending on the needs of log 206 and cache 104. Data 216 may include content associated with a cache block that is tracked in log 206. Examples of metadata 214 may include a memory address (for example, a logical block address (LBA)), a cache block type, an offset, and a hash value for error correction. An example of a cache block type may include tracking a cache block as an independent block or an associated block. An independent block and / or an associated block can be used with a content proximity cache. In some embodiments, the cache 104 may cache based on the similarity of the contents of a cache block (proximity of the content). An associated block can track changes, or differences, between the basic reference blocks. This caching of proximity content can furthermore make it possible to determine when a cache block was last used (time proximity) or to identify cache blocks with similar memory addresses (spatial proximity). An independent block may be a cached block based on temporal proximity and / or spatial proximity, but not proximity to content. The offset may identify a specific memory block of interest or a specific memory location of interest within a memory block. For example, the offset may be similar to a pointer in the data 216 which refers to specific data of interest.
    [0010] Because metadata 214 and data 216 can be combined into a single log block 212, journal writes can occur in streams or batches, and data and metadata writes can be combined into a single operation. 'writing. Storage of both metadata 214 and data 216 in a single log block 212 can thus provide a reduction of approximately 50% in write operations compared to having to write metadata 214 and data 216 separately. in different places. In some embodiments, the journal 206 may be a circular log. That is, cache 104 may write to log 206, generally sequentially, and when the end of log 206 is reached, the next write operation may return to a starting point to begin on next cycle. Metadata and data corresponding to write successes on cached data may be written to a new log block 212 in log 206. Sequential writes may be useful to avoid having to read the metadata otherwise 214 However, the sequential writes support may also mean that the log 206 may comprise a plurality of log blocks 212 that correspond to the same cache block. For example, a first write to the memory address 8 could be followed in the log block 1. A subsequent write to the same memory address, the memory address 8, could be followed in the log block 3 ( for example, if the cache 104 was handling Interim cache block updates that used the log block 2). Even though log blocks 1 and 2 also follow metadata and data corresponding to memory address 8, cache 104 can save processing time for existing log blocks. Instead, the design of the log 206 allows the cache 104 to write the entry for the log block 3 directly to the log 206 without having to read additional metadata. Therefore, sequential design can improve performance. The journal 206 can also generally support multiple storage devices. That is, log 206 does not distinguish between cache blocks of different cache storage target devices of interest. This multiple control medium can generally lead to better utilization of the space in the journal 206, since the multi-command medium generally eliminates the need to pre-reserve space for the different storage devices. Otherwise, the journal 206 could contain unused space that is pre-reserved for a storage device that did not need the space, which could lead to inefficient use of resources. However, a log 206 without invalidation data area 208 may also exhibit decreasing performance. An exemplary use case is that a cache 104 can cache multiple storage devices and operate in delayed write mode (i.e., post write cached update data in the underlying storage). If the eviction of the cache 104 to any of the storage devices fails, then the system can not cache new data, even new data for other storage devices. Instead, the system can preserve the old data so that it can be written offline to the storage device. The nonvolatile implementation based on the above described logging can generally be expected to be predicted sequentially. In some embodiments, the cache 104 can not discard data for an unavailable storage device unless the user explicitly requests the reverse.
    [0011] However, even with an unavailable storage device, cache 104 may continue to serve I / O operations to provide transparent service to other storage devices that are still available. This transparent caching can be performed as follows: 1) During a cache failure, cache 104 may cause the I / O operation to go through. 2) During successful reads, the cache 104 may serve the requested read operation from the cache 104. 3) Upon a successful write, the cache 104 may either (a) update or (b) invalidate the requested data from the cache.
    [0012] Either operation may lead to a read-modify-write cycle for the metadata 214, and a write operation for the data 216 (for example, in the case of an update request) . Thus, any success of writing could require a reading and a writing (for an invalidation) or 2 writings (for an update). Both scenarios may represent a penalty for overall performance. Each of these approaches may detract from the log-based approach using a log 206 without an invalid data area 208 for writing data. In addition, scenarios may present a risk of data loss because the operations are not atomic and could benefit from being run in series. Figure 2B illustrates an exemplary cache scheme diagram 104 in accordance with some embodiments of the present disclosure. Cache 104 may include an invalidation data area 208. Invalidating data area 208 may generally store invalidation records 218 for cache blocks that are deleted, or discarded, from cache 104. Invalidating data area 208 may include a separate cache region 104 (e.g., separate from journal 206). The system can map underlying log blocks in this separate region using invalidation records 218. In some embodiments, the cache may implement the separated region using a predetermined, dedicated space name. Accordingly, the invalidation data area 208 may have the following advantages: 1) Maintain a logging-based approach for writing log data. That is, the design of the invalidation data area 208 may convert write operations that would otherwise be potentially randomly updatable or invalidate writes to sequential writes to the cache device . 2) Map multiple log blocks into a single invalidation record block (shown in Figure 3A). For example, some embodiments of the invalidation data area 208 may map three log blocks into an invalidation record. Therefore, the space used for the invalidation data area 208 may be about 0.5% of a total cache size 104. 3) Because the size of the invalidation data area 208 may be a small fraction of the total size of the cache 104, the invalidation data area 208 may generally be stored entirely in a RAM. In addition, storing the invalidation data area in the RAM 208, in general, may eliminate the need for a read operation during the invalidation. Even though the invalidation data area is not typically stored in RAM, the system can still have a 66% reduction in the number of reads required. This is because records for three log blocks can be mapped to an invalidation block. 4) Packing invalidation record block entries can reduce the write system time, so that multiple entries are written in a single write operation. In addition, there may be a 66% reduction in the number of writes. Generally, the invalidation data area 208 may provide a transparent solution for error handling and maintaining data consistency. In addition, the invalidation data area 208 may offer these benefits without generally introducing a great loss of performance in exchange. Figure 3A illustrates an exemplary mapping between a log 206 and an invalid data area 208, in accordance with some embodiments of the present disclosure. Fig. 3A includes a log 206 and an invalidation data area 208. The log 206 includes log blocks 1-3. The invalidation data area 208 includes an invalidation record 1. The invalidation record 1 comprises mapped log blocks 1-3. In some embodiments, the invalidation records may generally be stored in the cache memory 104 in the separate invalidation data area. The invalidation records may generally use mapped log blocks associated with an invalidation record to represent multiple log blocks associated with the log 206. For example, the log block 1 may correspond to the mapped log block 1. Log block 2 may correspond to mapped log block 2, and log block 3 may correspond to mapped log block 3. In addition, mapped log blocks 1-3 may require less metadata to be stored than blocks. corresponding underlying journal 1-3. Accordingly, in some embodiments, the system can select a subset of metadata from underlying log blocks 1-3, so that all three mapped log blocks can be stored in the log record. Inhibition 1. Figure 3B illustrates another example of mapping between a log 206 and an invalidation data area 208, in accordance with some embodiments of the present disclosure. Fig. 3B includes a log 206 and an invalidation data area 208. The log 206 includes a log block 1 with metadata 214 and data 216. The invalidation data field 208 includes an invalidation record 1 The invalidation record 1 includes a mapped log block 1. The mapped log block 1 includes metadata 302.
    [0013] The invalidation record 1 may include both a version stored in a cache and a relatively faster version loaded into a RAM. The RAM data structure can generally improve performance and reduce the need to read data from the relatively slower log or from cache 104. In some embodiments, an example of invalidation record definition 1 may understand the following lines of code. / * As stored in cache 104 * / struct invalidation_record_block {unsigned char checksum [16]; // checksum of the entire syntax block struct mapped journal_block journal_block [3]; } An invalidation record example can include multiple logged log blocks ("log_block"), and an error correction code ("checksum"). In some embodiments of the invalidation record data structure, an example definition of the mapped log block referred to in the invalidation record data structure may include the following lines: struct mapped_journal_block {unsigned long long epoch; // newspaper time during writing. unsigned int target_lba [MAX_JOURNAL_ENTRY]; // offset storage (4000 LBAs aligned)} The mapped log block can include a collection (for example, a table) of memory addresses and offsets ("target_lba"). The memory addresses can identify a memory block of interest, and the offsets can identify specific memory blocks of interest or specific memory locations of interest in the memory blocks. The collection of memory addresses and offsets in the mapped log block can map a corresponding collection of memory addresses and offsets stored in underlying log blocks. The mapped log block may also include a timestamp ("epoch") that may correspond to a corresponding timestamp stored in the underlying log block. In some embodiments, the RAM data structure representing an invalidation record may include the following lines. / * Representation in invalidation record block RAM * / struct inraminvalidationrecordblock {unsigned char valid: 1; // if this block was written before unsigned char outstanding: 1; // The max. can only be 1 at any time. void * waiting creqs; // Wait for requests if there is already a pending write void * irb_cache_device; // Buffer containing the IRB on the cache device} The data RAM structure can generally improve performance and reduce the need to read data from the relatively slower log or from cache 104. The mapped log block can represent a log block. In some embodiments, an invalidation record may contain multiple mapped log blocks. For example, Figure 3A illustrates an invalidation record having a capacity of three mapped log blocks (so that there can be a 3-to-1 mapping from log blocks to an invalidation record). The mapped log block may store memory address entries that have been invalidated in the cache 104. In some embodiments, the memory addresses may be logical block addresses (LBAs). Although the present disclosure describes a tracking of three log blocks by means of a single invalidation record, the invalidation record may contain any number of mapped log blocks, for example determined on the basis of the subscript. metadata set chosen to be stored in the mapped log block. An example of a log block may be approximately 256 KB in size, and an example of an invalidation record may be approximately 4 KB in size. Because there may be 3-to-1 mapping between blocks log and invalidation records, the invalidation data area 208 must effectively manage the space. For example, the invalidation data area 208 may use only about 4 KB to account for the 768 KB (3 log x 256 KB blocks per log block) of data in the log 206. As a result, the space requirements for the invalidation data area 208 may be about 0.52% (4 KB / 768 KB). In addition, 3-to-1 mapping between log blocks mapped to invalidation records can reduce by approximately 66 percent the number of read and write operations performed during the invalidation process. In some embodiments, due to the small size of the invalidation data area 208 and the efficient allocation of space, the invalidation data area 208 may be stored entirely in random access memory (RAM) to reduce or even completely eliminate the number of read operations to the cache memory 104. In some embodiments, the invalidation data area 208 may store a subset of metadata 214 that is tracked in the journal 206. This can effectively help further reduce the size of the invalidation data area 208. For example, the metadata 214 tracked in the log 206 may include a memory address (e.g., a logical block address (LBA)), a type of cache block, an offset, and a hash value for error correction. In some embodiments, on the other hand, the metadata 302 tracked in the invalidation data area 208 may include a subset of metadata 214 tracked in the log 206. For example, the system may choose to track only a forward address. corresponding memory in metadata 302. Monitoring only a subset of metadata can improve the spatial efficiency or the capacity of the invalidation data area 208. Other changes depending on the uses and metadata stored in the journal 206 and the invalidation data area 208 may still affect this size. Examples of changes may include increasing the size of the log blocks, decreasing the size of the memory addresses stored in a mapped log block, and so on. Some embodiments of the system may truncate the size of the memory addresses stored in a mapped log block. In one implementation, truncation may be based on a storage size of the underlying storage device. For example, if the storage device is small enough, the system can store memory addresses of about four bytes in the mapped log block, relative to a fully expanded memory address of about eight bytes, stored in a memory. corresponding log block. In another implementation, truncation may include determining an offset based on a corresponding memory address used in the underlying storage, and storing the offset in place of the memory address. Cache implementations can store data blocks at sizes of approximately 4 KB. (If an I / O request is for a smaller size, then the cache can recover the remaining data associated with the block of data. data from the storage and can cache all of the content due 4K data block). Therefore, in some embodiments, truncation may include converting an underlying storage address (such as LBA) into offsets. In some embodiments, the offsets may be about 4 KB. For example, an offset of 0 may represent the first 4 KB on the storage device, an offset 1 may represent the next 4 KB on the storage device, and so on. . As a result, the cache can convert a memory address, for example, a 512-byte LBA, to an upcoming 4-KB aligned LBA. Rather than storing a full LBA, the system can convert a full LBA into an offset that uses a smaller number of bytes, and store the offset in the invalidation record the mapped log block. For example, LBA 0-7 in the underlying storage may match LBA 0 in the cache with an optional offset. In some embodiments of the invalidation data area, an offset field of size 4 B can thus address up to 16 terabytes of underlying storage (232 x 4096). For larger storage devices, some system implementations may increase the cache block size to about 8 KB or more, increase the offset size to about 5 bytes, and so on.
    [0014] Some cache embodiments 104 may invalidate cache blocks by determining a mapping between the log 206 and the invalidation data area 208. That is, the cache 104 may determine an appropriate invalidation record. a mapped log block, and a corresponding index in an invalid data area 208 for a data block, based on the log block and an index in the log 206.
    [0015] For example, suppose that the cache 104 invalidates a block of data residing in the log block 1 at index 3 (304a). Based on the log block and the index in the log 206, the cache 104 may generally determine the corresponding invalidation record, the mapped log block, and the index in the mapped log block. First, cache 104 may determine an invalidation record based on the corresponding log block. Because the log blocks can map 3 to 1 on the invalidation record capability, some embodiments of the cache 104 may perform a divide operation and a cap function (i.e. round) to determine the corresponding invalidation record. For example, for the log block 1, the system can calculate 1/3 = 0.33 ... and [0.331 = 1, which maps the log block 1 to the invalidation record 1. another example, if the system had mapped log block 5 to an invalidation record, 5/3 = 1.66 ... and [1.661 = -2, which maps log block 5 to invalidation record 2.
    [0016] Then, the cache 104 may determine a log block mapped based on a log block. In some embodiments, cache 104 may use a modulo operation to determine a log block mapped based on the log block number. For example, for the log block 1, the system can calculate 1 mod 3 = 1, which maps the log block 1 to the mapped log block 1. Similarly, if the system mapped the log block 5 to one mapped log block, 5 mod 3 = 2, which maps the log block 5 to the mapped log block 2 in an invalidation record 2 (as determined earlier). Finally, cache 104 may determine an index in the mapped log block that corresponds to an index in the underlying log block. Some embodiments of the cache 104 may use the same index in the mapped log block as the index used in the underlying log block. In other words, when writing the corresponding log block entries in the invalidation data field 208, the log block entries can be added to the same index in the "target lba" table of the mapped log block. , as used in a corresponding "target_lba" array of the log block. As a result, the index in the mapped log block can be easily and quickly determined based on the index in the underlying log block. To perform an inverse mapping (i.e., to determine a log block and a corresponding index based on an invalid record, a mapped log block, and an index), the cache 104 may perform the reverse operations of those described above. For example, cache 104 may identify information about a memory address for an invalid cache block based on the metadata 302 stored in the mapped log block. Cache 104 may determine the log block number based on the invalidation record number, and the index for the log block may be inferred from the index used in the mapped log block. Figure 4 illustrates an exemplary invalidation method 400 using the invalidation data area, in accordance with some embodiments of the present disclosure. In some embodiments, a method 400 may include determining a log block for a memory address in a received write operation (step 402); determining a mapped log block and an offset based on the determined log block and a corresponding invalidation record of the invalidation data area (step 404); determining whether there are outstanding write operations (step 406); if so, aggregate the write operations and execute the write operations as a single write to the cache (step 408); if not, execute the received write operation (step 410).
    [0017] First, the method 400 determines a log block for a memory address in a received write operation (step 402). Some embodiments of method 400 may identify the log block based on the logical block address (LBA) in the received write operation. Or, upon a write success (meaning that the LBA has been previously cached), the method 400 can identify the log block based on the LBA address to which the cache block is stored in. Cache. Then, the method 400 continues to determine a log block mapped based on the determined log block and a corresponding invalidation record of the invalidation data area (step 404). In some embodiments, the invalidation record may be determined by performing division operations and cap operations on the log block number. Some embodiments may also determine the index for the mapped log block using the index used in the underlying log block. For example, when the system uses the same indexes for the mapped log block and the underlying log block, the index can be determined easily and quickly. Then, method 400 can determine if there are outstanding write operations (step 406). In some embodiments, this can be determined using a random access memory (RAM) data structure corresponding to the invalidation record. For example, the RAM data structure may contain a field ("pending") which identifies whether write operations are pending. An advantage of using the data structure in RAM is to avoid a relatively slow read operation at the underlying cache memory to retrieve the stored invalidation record. If the method 400 determines that write operations are pending (step 406: Yes), the write operations and the execution of the write operations can be grouped into a single write on the cache (step 408) . Some embodiments of method 400 queues subsequent writes when determining that write operations are pending. After the previous write operation is complete, the method 400 writes the queued writes to the cache as a single write that contains the aggregated information of all the updates. In some embodiments, the aggregation may include identifying write operations that operate on the same block of data, controlling the write operations based on the timestamp, and determining the final result of the write operations. ordered write operations. In this way, this batch grouping or aggregation of write operations enables the method 400 to further reduce the number of read and write operations used for an invalidation. If it is determined that no write operation is pending (step 406: No), the method 400 may continue to execute the received write operation (step 410). Figure 5 illustrates an exemplary cache recovery method 500, in accordance with some embodiments of the present disclosure. Cache recovery refers to a situation in which the cache can benefit from log-based reconstruction and the invalidation data area, for example after a power failure, an improper system shutdown, or any other unplanned event. Method 500 may include rebuilding the cache based on the log (step 502); then, for each log block mapped in each invalidation record (step 504): determining whether a corresponding cache block is valid based on a mapped log entry (step 506); if so, return to step 504, if not, oust the erroneous block from the cache (step 508).
    [0018] First, the method 500 reconstructs the cache based on the log (step 502). Some embodiments of the system may assume that the log content typically represents valid data that must be reconstructed in the cache. In some embodiments, the system can reconstruct the cache by retrieving each log block from the log, and iterating metadata processing in each log block to reconstruct each cache block. However, log block metadata may actually contain cache blocks that may have been invalidated. The system may later correct this initial assumption of generally valid data based on the invalidation data area. For example, the system can identify invalid cache blocks based on the invalidation data area, and evict those cache blocks from the cache. Then, the method 500 iterates through each log block mapped in each invalidation record (step 504). For each mapped log block, the 10 metadata are processed in the mapped log block to determine whether the corresponding cache blocks are actually valid or invalid (step 506). Some embodiments may determine whether a cache block is valid by determining whether the metadata in the mapped log block is consistent with the underlying metadata in the underlying log block. For example, the consistency of the underlying metadata in the underlying log block can be determined by locating the corresponding log block number and index based on division operations, capping functions. and modulo operations. Then, the metadata stored at the determined log block number and the determined index can be prepared with the metadata stored in the mapped log block. For example, suppose the method 500 identifies, based on the mapped log block, that the memory address 8 should be found at the underlying log block 1, index 3. The method 500 can then retrieve the corresponding content of log block 1, at index 3 of the metadata. If this log block actually follows a cache block corresponding to a memory address 8, it can be determined that the cache block corresponding to the memory address 8 is invalid because the expected cache block based on the Invalidation data area and the mapped log block actually corresponds to the actual cache block tracked in the corresponding underlying log block. On the other hand, suppose that the method 500 identifies, on the basis of the mapped log block, that a cache block corresponding to the memory address 16 should be found at the underlying log block 1, index 4. If the actual cache block stored at the underlying log block 1, index 4, does not match the memory address 16, the process 500 may continue to process the next metadata because the cache block can remain in the cache when the expected cache block based on the invalidation data area and the mapped log block does not match the actual cache block tracked in the corresponding underlying log block. If the metadata matches, the method 500 may determine the invalid cache block (step 506: No). Accordingly, the method 500 can evict, or discard, the invalid (i.e., erroneous) block of the cache memory (step 508). If the metadata does not match, the method 500 may proceed to process the following metadata corresponding to the mapped log block, or continue to process the next mapped log block if the method 500 has processed all the metadata in the mapped log block ( step 506: Yes). The invalidation data area may further provide additional benefits around (1) transparent caching, and (2) dynamic cache mode switching between a delayed write mode and an immediate write mode . Transparent caching refers to the ability for an administrator or user to remove the system cache at will. Dynamic cache mode switching mode refers to the ability for an administrator or user to change the cache mode between a lazy write mode and an immediate write mode without having to shut down the system. The invalidation data area can enable transparent caching and dynamic mode switching without introducing significant latency at the current I / O operations. In some embodiments, the cache can avoid latency by discarding all data. If the cache is in writeback mode, the cache usually clears its erroneous data to the underlying storage device (ie, "write-backs" the data) before the cache can eliminate or evict the data. Previously, the cache emptied its data by pausing all pending I / O operations before flushing. However, stopping or pausing all pending I / O operations may introduce unwanted latency because there is no upper limit to the amount of time used for dump. Examples of factors that may affect the dump time may include the amount of erroneous data, randomness, disk speed, and so on. In some embodiments, the invalidation data area improves on-going I / O operations by pausing the cache and providing I / O operations as follows: cache failures 2) Cache serves read successes 3) The cache uses the invalidation data area to invalidate write successes and lets write to the underlying storage. After the cache flush is complete, the cache can discard all data safely.
    [0019] Those skilled in the art will appreciate that various illustrations described herein may be implemented in the form of electronic hardware, software, or a combination of both. To illustrate this interchangeability of hardware and software, various blocks of illustrative, modules, elements, components, methods, and algorithms have been described above generally in terms of their functionality. Whether this functionality is implemented in hardware, software or a combination of both depends on the particular application and design constraints imposed on the overall system. Skilled artisans can implement the described functionality in a variety of ways for each particular application. Various components and blocks can be arranged differently (they can for example be arranged in a different order, or distributed in another way), all without departing from the scope of the technology in question.
    [0020] In addition, an implementation of the invalidation data area can be performed centrally in a computer system, or in a distributed manner where different elements are distributed over a plurality of interconnected computer systems. Any type of computer system, or any other apparatus adapted to perform the methods described herein, is adapted to perform the functions described herein.
    [0021] A typical combination of hardware and software could be a universal computer system with a computer program that, when loaded and executed, controls the computer system to execute the methods described herein. The methods may also be incorporated into a computer program product, which includes all the functionality for implementing the methods described herein, and which, when loaded into a computer system, is capable of performing these methods.
    [0022] In the present context, "computer program" or "application" means any expression, in any language, code or notation, of a set of instructions intended to bring about a system having an information processing capability. to perform a particular function, either directly or after one or the other, or both of the following: a) conversion to another language, code or notation; (b) reproduction in a different material form. Significantly, the systems and methods described herein may also be embodied in other specific forms without departing from the essential spirit or attributes of the invention and, therefore, reference should be made to following claims, rather than the above specification, to indicate the scope of the systems and processes. The present invention has been described in detail with specific reference to these illustrated embodiments. It will, however, be obvious that various modifications and changes may be made while remaining within the spirit and scope of the invention as described in the foregoing specification, and such modifications and changes must be considered equivalent and of this description.
    权利要求:
    Claims (20)
    [0001]
    REVENDICATIONS1. Cache comprising: a log configured to track blocks of data stored in the cache; and an invalidation data area configured to track invalid data blocks associated with the data blocks tracked in the log, where the invalidation data area is in a region separate from the cache with respect to the log.
    [0002]
    The cache of claim 1, wherein the log is configured to track metadata for the data blocks, and wherein the metadata includes a memory address corresponding to the data block, and wherein the data area invalidation is configured to track metadata associated with the invalid data blocks, and wherein the associated metadata includes a memory address corresponding to the invalid data block. 15
    [0003]
    The cache of claim 2, wherein the log is configured to track the data blocks using log blocks, where the log blocks are configured to store the metadata for the data blocks; andin which the invalidation data area is configured to track the metadata associated with the invalid data blocks using invalid invalidation records and log blocks, where the mapped log blocks are configured to store the associated metadata for Invalid data blocks, and invalidate records are configured to store the mapped log blocks.
    [0004]
    The cache of claim 3, wherein the metadata tracked in the log further includes an index in a set of metadata stored in each log block, and wherein the metadata tracked in the invalidation data area further comprises an index in a set of metadata stored in each mapped log block.
    [0005]
    The cache of claim 3, wherein the cache is configured to determine an invalidation record number associated with an invalidation record in the invalidation data area based on a block number of Corresponding journal associated with a log block.
    [0006]
    The cache of claim 3, wherein the cache is configured to determine a mapped log block number associated with a log block mapped in the invalidation zone based on a corresponding associated log block number. to a newspaper block.
    [0007]
    The cache of claim 4, wherein the index track in the log is selected to have the same value as the index track in the invalidation data area.
    [0008]
    The cache of claim 1, wherein the memory address followed in the invalidation data area is truncated with respect to the memory address followed in the log, and in which truncation is determined based on at least one of a storage size of an underlying storage device being cached and a determined offset based on a memory address of a block in the underlying storage device .
    [0009]
    A method of disabling a block in a cache, the method comprising the steps of: determining a log block according to a memory address associated with a received write operation, the log block being stored in a cache log; determining a log block mapped based on the determined log block and further based on an invalidation record, the mapped log block and the invalidation record being stored in a data area d invalidate the cache; determine whether writing operations are pending; if write operations are pending, aggregate the outstanding write operations and execute a single write operation based on the aggregated write operations; and if there are no outstanding write operations, execute the received write operation.
    [0010]
    The method of claim 9, wherein determining the mapped log block includes determining a mapped log block number for the log block mapped to: determining an invalid log number by dividing a log block number. associated with the log block determined by a capacity of the invalidation record in the invalidation data area and calculating a cap function of the division result, the invalidation record number identifying the record of invalidation; and determining the mapped log block number by calculating a modulo operation of the log block number with the capability of the invalidation record.
    [0011]
    The method of claim 9, wherein determining whether write operations are pending includes recovering a field of a RAM data structure corresponding to the invalidation record.
    [0012]
    The method of claim 9, wherein aggregating outstanding write operations comprises the steps of: queuing subsequent write operations; identify write operations that operate on the same block of data; and determining the single write operation based on the write operations that operate on the same data block.
    [0013]
    The method of claim 9, wherein the invalidation data area is in a region separated from the cache with respect to the log.
    [0014]
    The method of claim 9, wherein the cache comprises a content proximity cache; and wherein the log follows at least one of the associated data blocks and independent data blocks in the content proximity cache.
    [0015]
    A method of recovering a cache, the method comprising the steps of: determining an initial cache rebuild based on a cache log; for each log block mapped in an invalidation record in a cache invalidation data area, determining whether a corresponding data block tracked in the log is valid, based on the mapped log block; and if the corresponding data block is determined to be invalid, discard the corresponding data block from the initial cache rebuild.
    [0016]
    The method of claim 15, wherein determining the initial reconstruction comprises retrieving data blocks and metadata describing the data blocks, retrieved data blocks and metadata being retrieved from the log.
    [0017]
    The method of claim 15, wherein determining whether the corresponding data block tracked in the log is valid includes comparing the metadata describing the corresponding data block tracked in the log to the metadata describing the corresponding data block followed in the block. of log mapped.
    [0018]
    The method of claim 17, wherein comparing the metadata comprises comparing a first memory address and a first index for the corresponding data block followed in the log to a second memory and a second index tracking in the mapped log block. .
    [0019]
    The method of claim 15, wherein the invalidation data area is in a region separate from the cache with respect to the log.
    [0020]
    The method of claim 15, wherein the cache comprises a content proximity cache; and wherein the log follows at least one of the associated data blocks and independent data blocks in the content proximity cache.
    类似技术:
    公开号 | 公开日 | 专利标题
    FR3023030B1|2019-10-18|INVALIDATION DATA AREA FOR CACHE
    US20190243558A1|2019-08-08|Two-level system main memory
    US10101930B2|2018-10-16|System and method for supporting atomic writes in a flash translation layer
    US9348760B2|2016-05-24|System and method for efficient flash translation layer
    EP2666111B1|2019-07-31|Storing data on storage nodes
    US10810123B1|2020-10-20|Flush strategy for using DRAM as cache media system and method
    FR3026512A1|2016-04-01|
    FR3033061A1|2016-08-26|
    US10095624B1|2018-10-09|Intelligent cache pre-fetch
    FR3020885A1|2015-11-13|
    US9442863B1|2016-09-13|Cache entry management using read direction detection
    US10521137B1|2019-12-31|Storage device array integration of dual-port NVMe device with DRAM cache and hostside portion of software stack system and method
    FR3027128A1|2016-04-15|
    US11061585B1|2021-07-13|Integration of NVMe device with DRAM cache system and method
    US11176034B2|2021-11-16|System and method for inline tiering of write data
    US10848555B2|2020-11-24|Method and apparatus for logical mirroring to a multi-tier target node
    FR3074317B1|2019-11-22|METHOD FOR ACCESSING A FLASH TYPE NON-VOLATILE MEMORY ZONE OF A SECURE ELEMENT, SUCH AS A CHIP CARD
    US20210034255A1|2021-02-04|System and method for sharing spare storage capacity between a log structured file system and raid
    More et al.2015|Dynamic Cache Resizing in Flashcache
    同族专利:
    公开号 | 公开日
    GB2546634A|2017-07-26|
    GB2540681A|2017-01-25|
    US20170068623A1|2017-03-09|
    GB2529035B|2017-03-15|
    US20150378925A1|2015-12-31|
    GB2546634B|2017-11-22|
    CN105302744B|2019-01-01|
    GB201509965D0|2015-07-22|
    CN105302744A|2016-02-03|
    GB201701188D0|2017-03-08|
    FR3023030B1|2019-10-18|
    GB2529035A|2016-02-10|
    DE102015007709A1|2015-12-31|
    US10810128B2|2020-10-20|
    US20210042235A1|2021-02-11|
    US20190317900A1|2019-10-17|
    GB2540681B|2017-06-14|
    US10445242B2|2019-10-15|
    US9501418B2|2016-11-22|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    WO1997001139A1|1995-06-23|1997-01-09|Elonex Plc|Disk array controller with enhanced synchronous write|
    AT361667T|1999-03-23|2007-06-15|Hibernation Therapeutics Ltd|STOP, PROTECT AND PRESERVE ORGANS|
    US7043610B2|2002-08-19|2006-05-09|Aristos Logic Corporation|System and method for maintaining cache coherency without external controller intervention|
    CN100377117C|2005-07-14|2008-03-26|中国科学院计算技术研究所|Method and device for converting virtual address, reading and writing high-speed buffer memory|
    CN100370440C|2005-12-13|2008-02-20|华为技术有限公司|Processor system and its data operating method|
    US7627713B2|2005-12-29|2009-12-01|Intel Corporation|Method and apparatus to maintain data integrity in disk cache memory during and after periods of cache inaccessibility|
    JP5104340B2|2007-04-24|2012-12-19|富士通株式会社|Computer apparatus and cache recovery method thereof|
    CN101201800B|2007-12-21|2010-06-09|福建星网锐捷网络有限公司|Data processing method and apparatus|
    US8275970B2|2008-05-15|2012-09-25|Microsoft Corp.|Optimizing write traffic to a disk|
    EP2180408B1|2008-10-23|2018-08-29|STMicroelectronics N.V.|Method for writing and reading data in an electrically erasable and programmable nonvolatile memory|
    US20110191522A1|2010-02-02|2011-08-04|Condict Michael N|Managing Metadata and Page Replacement in a Persistent Cache in Flash Memory|
    US20120215970A1|2011-02-22|2012-08-23|Serge Shats|Storage Management and Acceleration of Storage Media in Clusters|
    US9495301B2|2012-08-07|2016-11-15|Dell Products L.P.|System and method for utilizing non-volatile memory in a cache|
    US10055352B2|2014-03-11|2018-08-21|Amazon Technologies, Inc.|Page cache write logging at block-based storage|
    US9501418B2|2014-06-26|2016-11-22|HGST Netherlands B.V.|Invalidation data area for cache|US9501418B2|2014-06-26|2016-11-22|HGST Netherlands B.V.|Invalidation data area for cache|
    US11061876B2|2016-11-15|2021-07-13|Sap Se|Fast aggregation on compressed data|
    US10642796B2|2017-07-18|2020-05-05|International Business Machines Corporation|File metadata verification in a distributed file system|
    CN109284066A|2017-07-19|2019-01-29|阿里巴巴集团控股有限公司|A kind of data processing method, device, equipment and system|
    JP6731553B2|2017-07-20|2020-07-29|株式会社日立製作所|Distributed storage system and distributed storage control method|
    US10210086B1|2017-08-16|2019-02-19|International Business Machines Corporation|Fast cache demotions in storage controllers with metadata|
    US10877890B2|2018-06-01|2020-12-29|Intel Corporation|Providing dead-block prediction for determining whether to cache data in cache devices|
    US11237973B2|2019-04-09|2022-02-01|SK Hynix Inc.|Memory system for utilizing a memory included in an external device|
    KR20200132047A|2019-05-15|2020-11-25|에스케이하이닉스 주식회사|Apparatus and method for transmitting map information in memory system|
    KR20210014338A|2019-07-30|2021-02-09|에스케이하이닉스 주식회사|Data storage device, Data Processing System and operating method of Data storage device|
    法律状态:
    2016-06-27| PLFP| Fee payment|Year of fee payment: 2 |
    2017-05-11| PLFP| Fee payment|Year of fee payment: 3 |
    2018-05-11| PLFP| Fee payment|Year of fee payment: 4 |
    2018-12-07| PLSC| Search report ready|Effective date: 20181207 |
    2019-05-10| PLFP| Fee payment|Year of fee payment: 5 |
    2020-04-24| TP| Transmission of property|Owner name: WESTERN DIGITAL TECHNOLOGIES, INC., US Effective date: 20200319 |
    2020-05-12| PLFP| Fee payment|Year of fee payment: 6 |
    2021-05-13| PLFP| Fee payment|Year of fee payment: 7 |
    优先权:
    申请号 | 申请日 | 专利标题
    US14316256|2014-06-26|
    US14/316,256|US9501418B2|2014-06-26|2014-06-26|Invalidation data area for cache|
    [返回顶部]